use std::collections::HashMap;

pub enum ActionDirect {
    Start,
    Top,
    Right,
    Bottom,
    Left,
    NoFound,
}

#[derive(Debug, Clone, PartialEq)]
pub enum PointType {
    Start,
    End,
    Path,
    Wall,
    Edge,
}
#[derive(Debug, Clone)]
pub struct PathPoint {
    pub point: (usize, usize),
    pub cell_type: PointType,
    pub top_valid: Option<bool>,
    pub right_valid: Option<bool>,
    pub bottom_valid: Option<bool>,
    pub left_valid: Option<bool>,
}

impl PathPoint {
    pub fn new(point: (usize, usize), content: char) -> Self {
        PathPoint {
            point: point,
            cell_type: match content {
                'S' => PointType::Start,
                'E' => PointType::End,
                '.' => PointType::Path,
                '#' => PointType::Wall,
                _ => PointType::Edge,
            },
            top_valid: None,
            right_valid: None,
            bottom_valid: None,
            left_valid: None,
        }
    }
}

// #[derive(Debug)]
// pub struct PathPointVisited {
//     pub y: usize,
//     pub x: usize,
//     // true means used or bad
//     pub visited: bool,
// }

// impl PathPointVisited {
//     pub fn new(y: usize, x: usize, visited: bool) -> Self {
//         PathPointVisited {
//             y: y,
//             x: x,
//             visited: visited,
//         }
//     }
// }

pub fn solve_maze(
    maze: Vec<Vec<char>>,
    start: (usize, usize),
    end: (usize, usize),
) -> Vec<(usize, usize)> {
    // Your code here
    let mut path: Vec<(usize, usize)> = Vec::new();
    let mut failed_path: Vec<(usize, usize)> = Vec::new();
    //let mut record_path: Vec<(usize, usize, ActionDirect)> = Vec::new();
    let mut record_p: HashMap<(usize, usize), HashMap<(usize, usize), bool>> = HashMap::new();
    let mut is_dead_end = false;

    let maze_deep = maze.len();
    if maze_deep == 0 {
        return path;
    }
    let maze_width = maze[0].len();
    if maze_deep == 0 {
        return path;
    }
    let max_deep_idx = maze_deep - 1;
    let max_width_idx = maze_width - 1;

    let mut path_hm: HashMap<(usize, usize), PathPoint> = HashMap::new();

    for y in 0..maze_deep {
        for x in 0..maze_width {
            let mut c = PathPoint::new((y, x), maze[y][x]);
            if x == 0 || x == max_width_idx || y == 0 || y == max_deep_idx {
                if max_deep_idx == 0 {
                    c.top_valid = None;
                    c.bottom_valid = None;
                    if max_width_idx == 0 {
                        c.right_valid = None;
                        c.left_valid = None;
                    } else if x == 0 {
                        c.left_valid = None;
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else if x == max_width_idx {
                        c.right_valid = None;
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else {
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    }
                } else if y == 0 {
                    c.top_valid = None;
                    c.bottom_valid = match maze[y + 1][x] {
                        'S' | 'E' | '.' => Some(true),
                        _ => Some(false),
                    };
                    if max_width_idx == 0 {
                        c.right_valid = None;
                        c.left_valid = None;
                    } else if x == 0 {
                        c.left_valid = None;
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else if x == max_width_idx {
                        c.right_valid = None;
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else {
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    }
                } else if y == max_deep_idx {
                    c.bottom_valid = None;
                    c.top_valid = match maze[y - 1][x] {
                        'S' | 'E' | '.' => Some(true),
                        _ => Some(false),
                    };
                    if max_width_idx == 0 {
                        c.right_valid = None;
                        c.left_valid = None;
                    } else if x == 0 {
                        c.left_valid = None;
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else if x == max_width_idx {
                        c.right_valid = None;
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else {
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    }
                } else {
                    c.top_valid = match maze[y - 1][x] {
                        'S' | 'E' | '.' => Some(true),
                        _ => Some(false),
                    };
                    c.bottom_valid = match maze[y + 1][x] {
                        'S' | 'E' | '.' => Some(true),
                        _ => Some(false),
                    };
                    if max_width_idx == 0 {
                        c.right_valid = None;
                        c.left_valid = None;
                    } else if x == 0 {
                        c.left_valid = None;
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else if x == max_width_idx {
                        c.right_valid = None;
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    } else {
                        c.right_valid = match maze[y][x + 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                        c.left_valid = match maze[y][x - 1] {
                            'S' | 'E' | '.' => Some(true),
                            _ => Some(false),
                        };
                    }
                }
            } else {
                c.top_valid = match maze[y - 1][x] {
                    'S' | 'E' | '.' => Some(true),
                    _ => Some(false),
                };
                c.right_valid = match maze[y][x + 1] {
                    'S' | 'E' | '.' => Some(true),
                    _ => Some(false),
                };
                c.bottom_valid = match maze[y + 1][x] {
                    'S' | 'E' | '.' => Some(true),
                    _ => Some(false),
                };
                c.left_valid = match maze[y][x - 1] {
                    'S' | 'E' | '.' => Some(true),
                    _ => Some(false),
                };
            }
            //println!("{:?}", c);
            path_hm.insert((y, x), c);
            //cell_vec.push(c);
        }
    }

    let hh = path_hm;

    // review all p ('S', '.') , record valid p and visited status
    for p in hh.clone() {
        match p.1.cell_type {
            PointType::Start | PointType::Path => {
                let y = p.0 .0;
                let x = p.0 .1;
                let rp = record_p.entry((y, x)).or_insert(HashMap::new());
                if p.1.top_valid == Some(true) {
                    (*rp).entry((y - 1, x)).or_insert(false);
                }
                if p.1.right_valid == Some(true) {
                    (*rp).entry((y, x + 1)).or_insert(false);
                }
                if p.1.bottom_valid == Some(true) {
                    (*rp).entry((y + 1, x)).or_insert(false);
                }
                if p.1.left_valid == Some(true) {
                    (*rp).entry((y, x - 1)).or_insert(false);
                }
            }
            _ => {
                // no action
            }
        }
    }

    //println!("{:?}", record_p);

    path.push(start);
    //record_path.push((start.0, start.1, ActionDirect::Start));
    // check the cell's 4 direction, top, right, bottom, left
    let mut sear_y = start.0;
    let mut sear_x = start.1;
    //let mut t = 0;
    while true {
        let current_pp = hh.get(&(sear_y, sear_x)).unwrap();
        let cur_y = sear_y;
        let cur_x = sear_x;

        match current_pp.cell_type {
            PointType::End => break,
            PointType::Start if failed_path.len() != 0 => {
                is_dead_end = true;
                break;
            }
            _ => {
                if current_pp.top_valid == Some(true)
                    && !path.contains(&(sear_y - 1, sear_x))
                    && !failed_path.contains(&(sear_y - 1, sear_x))
                {
                    sear_y = sear_y - 1;
                } else if current_pp.right_valid == Some(true)
                    && !path.contains(&(sear_y, sear_x + 1))
                    && !failed_path.contains(&(sear_y, sear_x + 1))
                {
                    sear_x = sear_x + 1;
                } else if current_pp.bottom_valid == Some(true)
                    && !path.contains(&(sear_y + 1, sear_x))
                    && !failed_path.contains(&(sear_y + 1, sear_x))
                {
                    sear_y = sear_y + 1;
                } else if current_pp.left_valid == Some(true)
                    && !path.contains(&(sear_y, sear_x - 1))
                    && !failed_path.contains(&(sear_y, sear_x - 1))
                {
                    sear_x = sear_x - 1;
                } else {
                    // check this pp
                    if current_pp.cell_type == PointType::Start {
                        is_dead_end = true;
                        break;
                    }
                    if path.contains(&(sear_y, sear_x)) {
                        let bad_p = path.pop().unwrap();
                        failed_path.push(bad_p);
                        // use new p
                        (sear_y, sear_x) = path.pop().unwrap();
                    }
                }
                path.push((sear_y, sear_x));

                // if let Some(ref mut tmp_p1) = record_p.get(&(cur_y, cur_x)) {
                //     //println!("a1");
                //     if let Some(ref mut tmp_p2) = (*tmp_p1).get(&(sear_y, sear_x)) {
                //         //println!("a2");
                //         *(*tmp_p2) = true;
                //     }
                // }

                if let Some(tmp_p1) = record_p.get_mut(&(sear_y, sear_x)) {
                    if let Some(tmp_p2) = tmp_p1.get_mut(&(cur_y, cur_x)) {
                        *tmp_p2 = true;
                    }
                }

                if let Some(tmp_p1) = record_p.get_mut(&(cur_y, cur_x)) {
                    if let Some(tmp_p2) = tmp_p1.get_mut(&(sear_y, sear_x)) {
                        *tmp_p2 = true;
                    }
                }
            }
        };
        // println!("{:?}", path);
        // println!("{:?}", failed_path);
        // t += 1;
        // if t == 20 {
        //     break;
        // }
    }

    //println!("{:?}", record_p);

    let tj = exist_false_p(&record_p);

    if tj != ((0, 0), (0, 0)) {
        let mut new_path = path.clone();
        let mut t_0 = new_path.pop();
        while t_0 != Some(tj.0) {
            t_0 = new_path.pop();
        }
        new_path.push(tj.0);
        let abc = find_valid_path(&new_path, tj.1 .0, tj.1 .1, &hh, &mut record_p);
        println!("{:?}", abc);
    }

    // println!("{:?}", tj);

    if is_dead_end {
        path = Vec::new();
    }
    println!("{:?}", path);
    path
}

pub fn find_valid_path(
    start_path: &Vec<(usize, usize)>,
    sear_y: usize,
    sear_x: usize,
    hh: &HashMap<(usize, usize), PathPoint>,
    record_p: &mut HashMap<(usize, usize), HashMap<(usize, usize), bool>>,
) -> Vec<(usize, usize)> {
    let mut path = start_path.clone();
    let hh = hh.clone();
    let mut failed_path: Vec<(usize, usize)> = Vec::new();
    let mut is_dead_end = false;
    let mut sear_y = sear_y;
    let mut sear_x = sear_x;
    while true {
        let current_pp = hh.get(&(sear_y, sear_x)).unwrap();
        let cur_y = sear_y;
        let cur_x = sear_x;

        match current_pp.cell_type {
            PointType::End => break,
            PointType::Start if failed_path.len() != 0 => {
                is_dead_end = true;
                break;
            }
            _ => {
                if current_pp.top_valid == Some(true)
                    && !path.contains(&(sear_y - 1, sear_x))
                    && !failed_path.contains(&(sear_y - 1, sear_x))
                {
                    sear_y = sear_y - 1;
                } else if current_pp.right_valid == Some(true)
                    && !path.contains(&(sear_y, sear_x + 1))
                    && !failed_path.contains(&(sear_y, sear_x + 1))
                {
                    sear_x = sear_x + 1;
                } else if current_pp.bottom_valid == Some(true)
                    && !path.contains(&(sear_y + 1, sear_x))
                    && !failed_path.contains(&(sear_y + 1, sear_x))
                {
                    sear_y = sear_y + 1;
                } else if current_pp.left_valid == Some(true)
                    && !path.contains(&(sear_y, sear_x - 1))
                    && !failed_path.contains(&(sear_y, sear_x - 1))
                {
                    sear_x = sear_x - 1;
                } else {
                    // check this pp
                    if current_pp.cell_type == PointType::Start {
                        is_dead_end = true;
                        break;
                    }
                    if path.contains(&(sear_y, sear_x)) {
                        let bad_p = path.pop().unwrap();
                        failed_path.push(bad_p);
                        // use new p
                        (sear_y, sear_x) = path.pop().unwrap();
                    }
                }
                path.push((sear_y, sear_x));

                // if let Some(ref mut tmp_p1) = record_p.get(&(cur_y, cur_x)) {
                //     //println!("a1");
                //     if let Some(ref mut tmp_p2) = (*tmp_p1).get(&(sear_y, sear_x)) {
                //         //println!("a2");
                //         *(*tmp_p2) = true;
                //     }
                // }

                if let Some(tmp_p1) = record_p.get_mut(&(sear_y, sear_x)) {
                    if let Some(tmp_p2) = tmp_p1.get_mut(&(cur_y, cur_x)) {
                        *tmp_p2 = true;
                    }
                }

                if let Some(tmp_p1) = record_p.get_mut(&(cur_y, cur_x)) {
                    if let Some(tmp_p2) = tmp_p1.get_mut(&(sear_y, sear_x)) {
                        *tmp_p2 = true;
                    }
                }
            }
        };
    }
    path
}

pub fn exist_false_p(
    hm: &HashMap<(usize, usize), HashMap<(usize, usize), bool>>,
) -> ((usize, usize), (usize, usize)) {
    let mut r = ((0, 0), (0, 0));
    let tmp_hm = hm.clone();
    for t in tmp_hm.clone().into_iter() {
        let mut all_same = true;
        let mut tmp_j = true;
        let mut i = 1;
        for j in t.1.into_iter() {
            if i == 1 {
                tmp_j = j.1;
            }
            if !tmp_j.eq(&j.1) {
                all_same = false;
                break;
            }
            i += 1;
        }
        if !all_same {
            r.0 = t.0;
            break;
        }
    }

    if let Some(tmp_j) = tmp_hm.get(&(r.0)) {
        for j in tmp_j.clone().into_iter() {
            if !j.1 {
                r.1 = j.0;
                break;
            }
        }
    }
    r
}
